#ifndef __UNORDERED_MAP_H__
  #define __UNORDERED_MAP_H__

#include <vector>
#include <algorithm>

#include "exceptions.h"
using namespace std;

//! Unordered multimap implementation

/*!
This class offers the same functionality as std::multimap the only difference is that keys are not sorted so that
the order of elements will be untouched as they are inserted.
Elements are not unique in this collection.

Implementation date: 2007

Usage:

\code
unordered_map<int, string> um;
um.insert(5, "hi");
um.insert(5, "13246");
um.insert(-5, "hello");
\endcode
*/

template <class T, class U>
class unordered_map {
private:
  vector<T> keys;
  vector<U> values;

  //! assignment operator: not allowed
  //unordered_map &operator=(const unordered_map<T, U> &um);

  //! copy constructor: not allowed
  //unordered_map(const unordered_map<T, U> &um);

public:
  //! returns the number of items
  size_t size() const;

  //! deletes the first element of the collection
  void erase_first();

  //! deletes the last element of the collection. this is more efficient than erase_first
  void erase_last();

  //! deletes all items of the collection
  void clear();

  //! reserves enough place for the given number of items. this can improve performance
  void reserve(size_t items);

  //! finds the given key and return its index in the collection or SIZE_MAX if it is not found
  size_t find(const T &key) const;

  //! inserts the given key and its value to the collection. it doesn't matter if the key already exists or not, it can be inserted many times with different values
  void insert(const T &key, const U &value);

  //! removes the given key and its value from the collection. if the key does not exist, then this function will return false
  bool remove(const T &key);

  //! returns the key for the given index (may throw an exception)
  const T &get_key(size_t index) const;

  //! index operator (may throw an exception)
  U &operator[](size_t index);

  //! index operator (may throw an exception)
  const U &operator[](size_t index) const;

  //! default constructor
  unordered_map();

  //! destructor (non-virtual: please do not inherit from this class)
  ~unordered_map();
}; // class unordered_map

//////////////////////////////////////////////////////////////

template <class T, class U>
size_t unordered_map<T, U>::size() const {
  return keys.size();
} // unordered_map<T, U>::size

template <class T, class U>
void unordered_map<T, U>::erase_first() {
  if (keys.size() == 0)
    return;

  keys.erase(keys.begin());
  values.erase(values.begin());
} // unordered_map<T, U>::erase_first

template <class T, class U>
void unordered_map<T, U>::erase_last() {
  keys.pop_back();
  values.pop_back();
} // unordered_map<T, U>::erase_last

template <class T, class U>
void unordered_map<T, U>::clear() {
  keys.clear();
  values.clear();
} // unordered_map<T, U>::clear

template <class T, class U>
void unordered_map<T, U>::reserve(size_t items) {
  keys.reserve(items);
  values.reserve(items);
} // unordered_map<T, U>::reserve

template <class T, class U>
size_t unordered_map<T, U>::find(const T &key) const {
  typename vector<T>::const_iterator it = std::find(keys.begin(), keys.end(), key);

  if (it == keys.end())
    return -1; // or SIZE_MAX

  ptrdiff_t dif = it - keys.begin();
  return static_cast<size_t>(dif);
} // unordered_map<T, U>::find

template <class T, class U>
void unordered_map<T, U>::insert(const T &key, const U &value) {
  keys.push_back(key);
  values.push_back(value);
} // unordered_map<T, U>::insert

template <class T, class U>
bool unordered_map<T, U>::remove(const T &key) {
  const size_t index = find(key);
  if (index == SIZE_MAX)
    return false;

  keys.erase(keys.begin() + index);
  values.erase(values.begin() + index);
  return true;
} // unordered_map<T, U>::remove

template <class T, class U>
const T &unordered_map<T, U>::get_key(size_t index) const {
  if (index >= keys.size())
    throw index_exception(global_empty_string);

  return keys[index];
} // unordered_map<T, U>::get_key

template <class T, class U>
U &unordered_map<T, U>::operator[](size_t index) {
  if (index >= keys.size())
    throw index_exception(global_empty_string);

  return values[index];
} // unordered_map<T, U>::operator[]

template <class T, class U>
const U &unordered_map<T, U>::operator[](size_t index) const {
  if (index >= keys.size())
    throw index_exception(global_empty_string);

  return values[index];
} // unordered_map<T, U>::operator[]

template <class T, class U>
unordered_map<T, U>::unordered_map() {
  // nothing to do
} // unordered_map<T, U>::unordered_map

template <class T, class U>
unordered_map<T, U>::~unordered_map() {
  // nothing to do
} // unordered_map<T, U>::~unordered_map

#endif
